package leetcode.code0329;

public class Solution extends Solution329 {

	private int max;
	private int m;
	private int n;
	private int[][] matrix;
	private int[][] dp;

	@Override
	public int longestIncreasingPath(int[][] matrix) {
		max = 0;
		m = matrix.length;
		n = matrix[0].length;
		this.matrix = matrix;
		dp = new int[m][n];
		this.f(0, 0);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				this.f(i, j);
			}
		}
		return max;
	}

	private int f(int x, int y) {
		if (x >= m || x < 0 || y >= n || y < 0) {
			return 0;
		}
		if (dp[x][y] != 0) {
			return dp[x][y];
		}
		int ans = 1;
		int value = this.matrix[x][y];
		if (this.compare(value, x + 1, y)) {
			ans = Math.max(ans, this.f(x + 1, y) + 1);
		}
		if (this.compare(value, x - 1, y)) {
			ans = Math.max(ans, this.f(x - 1, y) + 1);
		}
		if (this.compare(value, x, y + 1)) {
			ans = Math.max(ans, this.f(x, y + 1) + 1);
		}
		if (this.compare(value, x, y - 1)) {
			ans = Math.max(ans, this.f(x, y - 1) + 1);
		}
		dp[x][y] = ans;
		this.max = Math.max(max, ans);
		return ans;
	}

	private boolean compare(int value, int x, int y) {
		if (x >= m || x < 0 || y >= n || y < 0) {
			return false;
		}
		return value > this.matrix[x][y];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
